package org.example;

public class Test1 {
    //leetcode 找出字符串中第一个匹配项的下标 https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150
    //kmp算法
    public int strStr(String str, String sub) {
        int n1 = str.length(), n2 = sub.length();
        if (n2 == 0) return 0; // 特殊情况：空子串
        int i = 0, j = 0;
        int[] next = getNext(sub);

        while (i < n1 && j < n2) {
            if (j == -1 || str.charAt(i) == sub.charAt(j)) { // 若 j == -1，则直接向前移动
                i++;
                j++;
            } else {
                j = next[j]; // 回退到 next 数组中的位置
            }
        }
        return (j == n2) ? i - n2 : -1; // 如果匹配完成，返回起始位置
    }

    public int[] getNext(String s) {
        int[] next = new int[s.length()];
        next[0] = -1; // 初始化 next[0] 为 -1
        int k = 0, i = 2;

        while (i < s.length()) {
            if (k == -1 || s.charAt(i - 1) == s.charAt(k)) {
                k++;
                next[i] = k;
                i++;
            } else {
                k = next[k]; // 回退到前一个部分匹配的位置
            }
        }
        return next;
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        String s = "aabaaac";
        int[] ret = test1.getNext(s);
        System.out.println(666);
    }
}
